package cn.edu.xjtu.carlWay.dynamicProgramming.partitionEqualSubsetSum;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 */
public class Solution_backtrace {
    public static void main(String[] args) {
        Solution_backtrace solution = new Solution_backtrace();
        int[] nums = {1, 5, 11, 5};
//        int[] nums = {1, 2, 3, 5};
        System.out.println(solution.canPartition(nums));
    }

    int sum = 0;// 当前总数
    int left;// 剩余的总数
    boolean flag;

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) {
            return false;
        }
        left = sum;
        Arrays.sort(nums);
        backtrack(nums, 0, sum / 2);
        return flag;
    }

    private void backtrack(int[] nums, int index, int target) {
        if (sum == target) {
            flag = true;
        } else {
            for (int i = index; i < nums.length; i++) {
                if (sum + left < target) {
                    break;
                }
                left -= nums[i];
                if (sum + nums[i] <= target) {
                    sum += nums[i];
                    backtrack(nums, i + 1, target);
                    sum -= nums[i];
                }
                left += nums[i];
            }
        }
    }
}
